1. Technical Field
The present disclosure relates to searching in an image database for an object visually similar to an object in a given reference image.
2. Description of the Related Art
Significant developments have recently been made in the field of visual search in particular so that such a search can overcome differences in position in the image, and differences of scale and direction in space, and then be performed using relatively limited computing means, such as those provided in smartphones. The SIFT (Scale-Invariant Feature Transform) and SURF (Speed-Up Robust Features) algorithms have particularly brought major developments in this field. To find identical or similar objects in different images, these algorithms suggest applying a processing operation to each image to be compared, e.g., to the reference image and to each image in the image database. This processing aims to detect characteristic points in the image, then to determine for each characteristic point, a descriptor describing the region around the characteristic point. The search for characteristic points is based on the detection in the image at different scales of locally extreme contrast points, e.g., bright points in the dark areas and dark points in the bright areas.
A characteristic point descriptor is in the form of a vector gathering spatial information relating to a region of the image around the characteristic point. Such a descriptor can be considered a visual signature of the region around the corresponding characteristic point. The position in the image of each characteristic point and its descriptor are stored in the image database in association with each image.
The actual visual search comprises a comparison of each descriptor of the reference image with all or part of the descriptors of each image in the image database. As the descriptors are vectors in the mathematical sense of the word, this comparison may comprise a calculation of a vector difference scalar product or norm. When two descriptors are considered sufficiently close or similar according to certain criteria, the corresponding characteristic points can be considered similar. A geometrical verification is then performed to eliminate points that have been considered similar but do not correspond to a same object appearing on the two images. This verification comprises a step of determining whether a constellation formed by a sub-set of similar points, extracted from one of the two images to be compared, appears in the other image, seen from a different angle, and/or at a different scale, and/or in a different spatial configuration. The characteristic points having no match, given a certain tolerance, in the two images to be compared using this affine transformation are eliminated.
The RANSAC (RANdom SAmple Consensus) algorithm can be used for this purpose to determine in a few iterations an affine transformation model, capable of linking two constellations of characteristic points in the two images to be compared. This algorithm comprises a step of selecting a group of a certain number of characteristic points sufficiently close (similar) in the two images. The chosen number of points can be a minimum number required to determine an affine transformation model. This algorithm further comprises a step of determining the parameters of the transformation model from these points, and of searching among the other similar characteristic points for those corresponding to the transformation model considering a certain tolerance. These steps are executed with other different groups of characteristic points, a certain number of times or until a sufficient number of points is found. The model corresponding to the greatest number of similar characteristic points is considered the best model and all the similar characteristic points that do not correspond to the model are rejected. A final match rating between the two compared images is then calculated. This rating can correspond either to the number of similar characteristic points corresponding to the transformation model thus determined, or to the surface area of the portion of image surrounding all the similar characteristic points corresponding to the transformation model. This surface area corresponds to the surface area of an object represented in the two compared images.
Each image in the image database can thus be associated with a match rating of the match with the reference image. The images having the best rating can thus be supplied in response to a visual search request comprising the reference image.